/**
 * 给一个group数组，给一个element数组 
 * 对group中的每一个元素Ai，在element中找Ai的因子，如果有多个，返回第一个
 * 显然不能遍历group，去拆分Ai。
 * 跟因子有关，可以考虑筛法。
 * 遍历element中的每一个Ei：
 *   将[Ei, LIMIT]中所有Ei的倍数均设置为i
 * 加一个标记数组，只处理值相同的第一个Ei
 * 预处理最差情况下就是筛法，NlogN的
 * 然后在遍历group查看即可
 */
class Solution {
public:
    vector<int> assignElements(vector<int>& groups, vector<int>& elements) {
        using vi = vector<int>;
        int m = *max_element(groups.begin(), groups.end());

        vi used(m + 1, 0);
        vi flag(m + 1, -1);
        for(int i=0;i<elements.size();++i){
            auto e = elements[i];
            if(e > m or used[e]) continue;

            used[e] = 1;
            for(int j=e;j<=m;j+=e){
                if(flag[j] == -1)flag[j] = i;
            }
        }

        int n = groups.size();
        vi ans(n, -1);
        for(int i=0;i<n;++i){
            ans[i] = flag[groups[i]];
        }
        return ans;
    }
};